package com.yileiqian.alg;

import java.util.List;
import java.util.ArrayList;

public class CommonSubArray {

	public static int[] getCSA(int[] a, int[] b) {
		List<Integer> out = new ArrayList<Integer>();

		int p1 = 0;
		int p2 = 0;

		while (p1 < a.length && p2 < b.length) {
			if (a[p1] > b[p2]) {
				p2++;
			} else if (a[p1] < b[p2]) {
				p1++;
			} else if (a[p1] == b[p2]) {
				break;
			}
		}

		while (a[p1] == b[p2]) {
			out.add(a[p1++]);
			p2++;
		}

		int[] c = new int[out.size()];
		for (int i = 0; i < c.length; i++) {
			c[i] = out.get(i);
		}
		return c;
	}

	public static void main(String args[]) {
		int a[] = { 0, 1, 2, 3, 4, 6, 8, 9 };
		int b[] = { 2, 3, 4, 5, 6, 9 };

		int c[] = getCSA(a, b);

		for (int i = 0; i < c.length; i++) {
			System.out.print(c[i] + " ");
		}
	}
}